#include <vector>
#include <queue>

using namespace std;

struct cmp {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
        for (auto it : lists) {
            if (it == nullptr) { continue; }
            heap.push(it);
        }
        if (heap.empty()) {
            return nullptr;
        }
        ListNode* res = new ListNode, * rear = res;
        while (heap.size()) {
            rear->next = heap.top();
            heap.pop();
            if (rear->next->next != nullptr) {
                heap.push(rear->next->next);
            }
            rear = rear->next;
        }
        rear = res;
        res = res->next;
        delete rear;
        return res;
    }
};